package  fina.indextree;
public class NumArray {
    int[] sum;
    int[] arr;
    int MAXN;

    public NumArray(int[] nums) {
        MAXN = nums.length + 1;
        sum = new int[MAXN];
        arr = new int[MAXN];
        for(int i = 1;i < MAXN;i++ ){
            arr[i] = nums[i - 1];
            add(i,nums[i - 1]);
        }
    }
    public void add(int index,int val){
        while (index < MAXN){
            sum[index] += val;
            index += (index & -index);
        }

    }
    public int sum(int index){
        int res = 0;
        while (index > 0){
            res += sum[index];
            index -= (index & -index);
        }
        return res;
    }

    public void update(int index, int val) {
        ++index;
        int n = val - arr[index];
        arr[index] = val;
        add(index,n);
    }

    public int sumRange(int left, int right) {
        return sum(++right) - sum(left);
    }
}